package com.xy6.struct.queue;

import java.util.Arrays;

/**
 * 优先队列类（最大优先队列）
 * <p>基于堆实现
 * <p>插入O(lgn)，删除O(1)，查找O(lgn)
 * 
 * @author internet
 * @since 2017-09-04
 */
public class PriorityQueue2 {

    private int[] arr;
    private int size;


    /**
     * 优先队列数组默认大小为64
     */
    public PriorityQueue2() {
        this(64);
    }

    public PriorityQueue2(int initSize) {
        if (initSize <= 0) {
            initSize = 64;
        }
        this.arr = new int[initSize];
        this.size = 0;
    }

    /**
     * 查看最大值
     * 
     * @return
     */
    public int peek() {
        return this.arr[0];
    }

    /**
     * 弹出最大值
     * 
     * @return
     */
    public int pop() {
        int t = peek();

        this.arr[0] = this.arr[--size];
        shifDown(0, this.arr[0]);
        return t;
    }
    
    /**
     * 添加一个元素
     * 
     * @param data
     */
    public void push(int data) {
        resize(1);
        this.arr[size++] = data;
        shifUp(size - 1, data);
    }
    
    public int size(){
    	return size;
    }

	public void print(){
		for(int i=0; i<size; i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
	
    /**
     * 元素下沉
     * <pre>
     * 找到两个子节点中较大的一个节点；
     * 比较根节点与子节点；
     * 如果根节点比子节点大，则节点已满足堆规则，调整完毕；
     * 如果根节点比子节点小，则与子节点进行交换；
     * 找到两个子节点中较大的一个节点；
     * 重复上述步骤，直至遍历至集合最后一个元素，或者满足堆规则，调整完毕。
     * </pre>
     * 
     * @param i 索引
     * @param key 值
     */
    private void shifDown(int i, int key) {
        while (2 * i + 1 <= this.size - 1) {
            int child = 2 * i + 1;
            if (child < this.size - 1 && this.arr[child] < this.arr[child + 1]) {
                child++;
            }
            if (this.arr[i] >= this.arr[child]) {
                break;
            }

            swap(i, child);
            i = child;
        }
    }

    /**
     * 元素上浮
     * <pre>
     * 找到父节点；
     * 将当前节点与父节点进行比较；
     * 如果当前节点比父节点小，则已满足堆规则，调整结束；
     * 如果当前节点比父节点大，则交换；
     * 找到父节点；
     * 重复上述步骤，直至遍历至集合第一个元素，或者满足堆规则，调整完毕。
     * </pre>
     */
    private void shifUp(int i, int key) {
        while (i > 0) {
			int parent = (i - 1) / 2;
            if (this.arr[i] <= this.arr[parent]) {
                break;
            }
            swap(i, parent);
            i = parent;
        }
    }

    /**
     * 重新调整数组大小
     */
    private void resize(int increaseSize) {
        if ((this.size + increaseSize) > this.arr.length) {
            int newSize = (this.size + increaseSize) > 2 * this.arr.length ? (this.size + increaseSize) : 2 * this.arr.length;
            int[] t = this.arr;

            this.arr = Arrays.copyOf(t, newSize);
        }
    }

    /**
     * Swaps arr[a] with arr[b].
     */
    private void swap(int a, int b) {
        int t = this.arr[a];
        this.arr[a] = this.arr[b];
        this.arr[b] = t;
    }
}